﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * 
     * We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

     * 
     * 
     * */
    class Problem32
    {
        public static string Calculate()
        {
            List<int> digits = new List<int>();

            for (int i = 1; i <= 9; i++)
                digits.Add(i);


            List<int> products = new List<int>();
            List<int> a = new List<int>();
            List<int> b = new List<int>();

            //treba nac pandigitalne a*b = c;
            //oni koji zadovoljavaju su a - 1 znamenka, b - 4 znamenke, c-4 znamenke
            for (int i = 1; i < 10; i++)
            {
                var permutations = GetPermutations(digits.Where(x => x != i).ToList(), 4); //gdje nisu od ove znamenke

                foreach (int permutation in permutations)
                {
                    int product = permutation * i;
                    var productDigits = GetDigits(product);

                    var remainingDigits = digits.Where(x => x != i && !GetDigits(permutation).Contains(x)).ToList();

                    if (productDigits.Count != remainingDigits.Count)
                        continue;

                    bool match = true;

                    foreach (int digit in productDigits)
                    {
                        if (remainingDigits.Contains(digit))
                        {
                            remainingDigits.Remove(digit);
                        }
                        else
                        {
                            match = false;
                            break;
                        }
                    }

                    if (match)
                    {
                        products.Add(product);
                        a.Add(i);
                        b.Add(permutation);
                    }
                }
            }

            //drugi koji zadovoljavaju su aa*bbb=cccc;

            var apermutations = GetPermutations(digits, 2);

            foreach (int aNumber in apermutations)
            {
                var aDigits = GetDigits(aNumber);
                var bpermutations = GetPermutations(digits.Where(x => !aDigits.Contains(x)).ToList(), 3); //gdje nisu od ove znamenke

                foreach (int permutation in bpermutations)
                {
                    int product = permutation * aNumber;
                    var productDigits = GetDigits(product);

                    var remainingDigits = digits.Where(x => !aDigits.Contains(x) && !GetDigits(permutation).Contains(x)).ToList();

                    if (productDigits.Count != remainingDigits.Count)
                        continue;

                    bool match = true;

                    foreach (int digit in productDigits)
                    {
                        if (remainingDigits.Contains(digit))
                        {
                            remainingDigits.Remove(digit);
                        }
                        else
                        {
                            match = false;
                            break;
                        }
                    }

                    if (match)
                    {
                        products.Add(product);
                        a.Add(aNumber);
                        b.Add(permutation);
                    }
                }
            }

            for (int i = 0; i < products.Count; i++)
            {
                Console.WriteLine("{0} * {1} = {2}", a[i], b[i], products[i]);
            }

            return products.Distinct().Sum().ToString();
        }

        /// <summary>
        /// Daje sve permutacije duljine k napravljene od navedenih znamenki.
        /// Broj permutacije je n!/(n-k)!, pa oprezno!
        /// Trebale bi bit poredane od manje prema većoj (odnosno, poredane su kako su ulazne znamenke poredane)
        /// </summary>
        /// <param name="digits">Znamenke koje smijemo upotrebljavat (n je broj znamenki u ovoj listi)</param>
        /// <param name="k">Duljina kombinacije</param>
        /// <returns>Sve permutacije duljine k</returns>
        public static List<int> GetPermutations(List<int> digits, int k)
        {
            List<int> permutations = new List<int>();

            if (k == 0)
                return permutations;

            if (digits.Count == 1)
            {
                permutations.Add(digits[0]);
            }
            else
            {
                for (int i = 0; i < digits.Count; i++)
                {
                    var sub = GetPermutations(digits.Where((x, ind) => ind != i).ToList(), k - 1);

                    if (sub.Count == 0)
                        permutations.Add(digits[i]);

                    foreach (int comb in sub)
                    {
                        permutations.Add(comb * 10 + digits[i]);
                    }
                }
            }
            return permutations;
        }

        /// <summary>
        /// Daje sve permutacije brojeva koji sadrže odabrane znamenke
        /// Broj permutacija je n!, pa oprezno :)
        /// Trebale bi bit poredane od manje prema većoj (odnosno, poredane su kako su ulazne znamenke poredane)
        /// </summary>
        /// <param name="digits">Znamenke koje smijemo upotrebljavat (n je broj znamenki u ovoj listi)</param>
        /// <returns>Listu permutacija</returns>
        public static List<int> GetPermutations(List<int> digits)
        {
            List<int> premutations = new List<int>();

            if (digits.Count == 1)
            {
                premutations.Add(digits[0]);
            }
            else
            {
                for (int i = 0; i < digits.Count; i++)
                {
                    var sub = GetPermutations(digits.Where((x, ind) => ind != i).ToList());
                    foreach (int comb in sub)
                    {
                        premutations.Add(comb * 10 + digits[i]);
                    }
                }
            }

            return premutations;
        }

        /// <summary>
        /// Daje listu znamenki nekog broja.
        /// </summary>
        /// <param name="number">Broj čije znamenke hoćemo.</param>
        /// <returns>Listu znamenki.</returns>
        public static List<int> GetDigits(int number)
        {
            List<int> result = new List<int>();
            while (number != 0)
            {
                result.Add(number % 10);
                number /= 10;
            }

            return result;
        }
    }
}
